package com.chapter4.graph.mst;

import java.util.PriorityQueue;

import com.chapter1.basic.analysis.QuickUnionImprove;
import com.chapter1.basic.queue.Queue;

/**
 * 
* @ClassName: KruskalMST 
* @Description: kruskal算法解决MST问题
* 
* 按照从小到大的顺序，依次标记无向图所有边（按权重来排列），如果新标记的的边会使得图 中产生环路，则忽略掉这条边，继续标记后面的边
*  
* @author minjun
* @date 2015年3月7日 下午4:57:56 
*
 */
public class KruskalMST {

	//权重
	private double weight;
	
	private Queue<Edge> edges;

	public KruskalMST(WeightEdgeGraph g){
		PriorityQueue<Edge> queue=new PriorityQueue<Edge>();
		
		for(Edge e:g.edges()){
			queue.add(e);
		}
		edges=new Queue<Edge>();
		QuickUnionImprove qui=new QuickUnionImprove(g.V());
		while(!queue.isEmpty()&&edges.size()<g.V()-1){
			Edge e=queue.poll();
			int m=e.either();
			int n=e.other(m);
			//如果之前并没有形成两个点连接，就表示新加入标记的边不会使得图产生环路
			if(!qui.connected(m, n)){
				//使得两点相连
				qui.union(m, n);
				edges.offer(e);
				weight+=e.weight();
			}
		}
	}
	
	public Iterable<Edge> edges(){
		return edges;
	}
	
	public double weight(){
		return weight;
	}
}
